package com.jake.data_structure_learning.sort;

/**
 * copyright (C), 2021, 武汉德辞信息技术有限公司
 *
 * @author WangXiang
 * @version 1.0.0
 * @create 2021/6/23 14:54
 * @description <author>                <time>                  <version>
 * WangXiang               2021/6/23 14:54            1.0.0
 */
public class SortV2 {

    /**
     * 冒泡排序
     *
     * @param nums
     */
    public static void bubbleSort(int[] nums) {
        int temp;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     *
     * @param nums
     */
    public static void selectSort(int[] nums) {
        int min;
        int index;
        for (int i = 0; i < nums.length - 1; i++) {
            min = nums[i];
            index = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    index = j;
                }
            }

            if (index != i) {
                min = nums[i];
                nums[i] = nums[index];
                nums[index] = min;
            }
        }
    }

    /**
     * 插入排序
     *
     * @param nums
     */
    public static void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    int temp = nums[i];
                    System.arraycopy(nums, j, nums, j + 1, i - j);
                    nums[j] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     *
     * @param nums
     */
    public static void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public static void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int key = nums[start];
            int index = start;
            for (int i = start + 1; i <= end; i++) {
                if (nums[i] < key) {
                    int temp = nums[i];
                    nums[i] = nums[index];
                    nums[index] = temp;
                    index++;
                }
            }
            quickSort(nums, start, index);
            quickSort(nums, index + 1, end);
        }
    }


    /**
     * 归并排序
     *
     * @param nums
     */
    public static void mergeSort(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
    }

    public static void mergeSort(int[] nums, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(nums, start, mid);
            mergeSort(nums, mid + 1, end);
            merge(nums, start, mid, end);
        }
    }

    public static void merge(int[] nums, int start, int mid, int end) {
        int[] temp = new int[nums.length];
        int _left = start;
        int _right = mid + 1;
        int index = _left;
        while (_left <= mid && _right <= end) {
            if (nums[_left] < nums[_right]) {
                temp[index++] = nums[_left++];
            } else {
                temp[index++] = nums[_right++];
            }
        }

        while (_left <= mid) {
            temp[index++] = nums[_left++];
        }

        while (_right <= end) {
            temp[index++] = nums[_right++];
        }

        for (int i = start; i <= end; i++) {
            nums[i] = temp[i];
        }
    }

    /**
     * 位图排序
     *
     * @param nums
     */
    public static void bitmapSort(int[] nums) {
        int max = findMaxValue(nums);
        int length = max / 32 + 1;
        int[] bitMap = new int[length];
        for (int i = 0; i < nums.length - 1; i++) {
            setValue(bitMap, nums[i]);
        }

        for (int i = 0; i <= max; i++) {
            if (readValue(bitMap, i) == 1) {
                System.out.println(i);
            }
        }
    }

    public static int findMaxValue(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
        }
        return max;
    }

    public static void setValue(int[] bitMap, int value) {
        int position = value / 32;
        int index = value % 32;
        bitMap[position] |= (1 << index);
    }

    public static int readValue(int[] bitMap, int value) {
        int index = value % 32;
        int position = value / 32;
        int result = (bitMap[position] >> index) & 1;
        return result;
    }
}
